package ali;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 102. 二叉树的层序遍历
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 * @author wxh
 */
public class Solution_5 {

	/**
	 * 思路1：BFS广度优先搜索的思路
	 */
	public List<List<Integer>> levelOrder(TreeNode root) {

		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (root == null) {
			return result;
		}

		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);

		// 注意，如果是图，则需要记录访问过的节点
//		List<Integer> visited = new ArrayList<Integer>();

		while (!queue.isEmpty()) {
			List<Integer> levelList = new ArrayList<Integer>();
			int currentLevelSize = queue.size(); //从队列大小可以知道，当前层级有多少个元素
			for (int i = 0; i < currentLevelSize; i++) {
				TreeNode treeNode = queue.poll(); // 获取并移除队头元素
				levelList.add(treeNode.val);

				// 检查是否存在左右子节点，存在则入队列
				if (treeNode.left != null) {
					queue.offer(treeNode.left);
				}
				if (treeNode.right != null){
					queue.offer(treeNode.right);
				}
			}
			result.add(levelList);
		}
		return result;

	}

	/**
	 * 思路2：DFS深度优先搜索（展示算法功底，开阔思维用）
	 */
	public List<List<Integer>> levelOrder2(TreeNode root) {

		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (root == null) {
			return result;
		}

		dfs(result, root, 0);
		return result;

	}

	public void dfs(List<List<Integer>> result, TreeNode root, int level) {

		// 递归终止条件
		if (root == null) {
			return;
		}

		// 如果result集合小于等于当前行，说明当前层还没有任何结果，需要初始化一个子集合，来装这一层的数据
		if (result.size() <= level) {
			result.add(new ArrayList<>());
		}

		// 把当前层遍历到的节点，放入当前层的子集合
		result.get(level).add(root.val);

		// 继续递归左右节点
		dfs(result, root.left, level + 1);
		dfs(result, root.right, level + 1);

	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

}